package lc20240525;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class InsertSection {
    public static void main(String[] args) {
        int[][] array = {
                {1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}
        };
        int[][] array1 = {
                {1, 3}, {6, 9}
        };

        int[] newInterval = {2, 5};
        System.out.println(Arrays.deepToString(insert1(array1, newInterval)));

    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        int h = intervals.length;
        int[][] res = Arrays.copyOf(intervals, h + 1);
        System.out.println(Arrays.deepToString(res));
        //插入的位置
        int index = 0;
        for (int i = 0; i < h; i++) {
            if (newStart < intervals[i][0]) {
                index = i;
            }
        }
        for (int i = h; i > index; i--) {
            res[i] = res[i - 1];
        }
        res[index] = newInterval;
        return merge(res);
    }

    public static int[][] merge(int[][] intervals) {
        //排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> list = new ArrayList<>();
        int[] curInt = intervals[0];
        list.add(curInt);
        for (int[] ints : intervals) {
            int curEnd = curInt[1];
            int nextStart = ints[0];
            int nextEnd = ints[1];
            if (curEnd >= nextStart) {
                curInt[1] = Math.max(nextEnd, curEnd);
            } else {
                list.add(ints);
                curInt = ints;
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    public static int[][] insert1(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        //局部变量
        int i = 0;
        //添加前面的
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }
        int start = newInterval[0];
        int end = newInterval[1];
        //合并区间
        //更新开始和结束，分别取最小最大值，注意条件的判断。小于等于。聚合函数里面要把要更新的值放在里面，start要同步更新。
        //不能是intervals[i][]和newInterval[0]比较。
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            start = Math.min(intervals[i][0], start);
            end = Math.max(intervals[i][1], end);
            i++;
        }
        res.add(new int[]{start, end});

        /*  //也可以这么写
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res.add(newInterval);*/


        while (i < intervals.length && intervals[i][0] > newInterval[1]) {
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(new int[res.size()][]);
    }
}
